#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'
const int maxn = 4;
int n = 4, m = 4;
char G[maxn][maxn] = {  //平面图 矩形 默认行为n 列为m
        'A', 'B', 'C', 'D',
        'E', 'F', '/', '/',
        '/', '/', 'K', '/',
        'M', '/', '/', 'P'
};
int book[maxn][maxn];
int fx[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};//四连通 顺时针方向
pair<int, int> F[100][100];

pair<int, int> Find(const pair<int, int> &pt) {
    if ( F[pt.first][pt.second] == pt ) {
        return pt;
    }
    return F[pt.first][pt.second] = Find(F[pt.first][pt.second]);

};

bool Merge(const pair<int, int> & p, const pair<int, int> & q) {
    auto rootp = Find(p);
    auto rootq = Find(q);
    if ( rootp == rootq ) {
        return false;
    }
    F[rootp.first][rootp.second] = rootq;
    return true;
}

int Count() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            auto p = make_pair(i, j);
            if ( G[p.first][p.second] == '/' )continue;
            if ( p == F[p.first][p.second] ) {
                cerr << "root=" << G[p.first][p.second] << endl;
                ++cnt;
            }

        }
    }
    return cnt;
}

void Init() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            auto p = make_pair(i, j);
            F[p.first][p.second] = p;

        }
    }
}

int main() {
    Init();
   // cout << "Cnt=" << Count() << endl;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if ( G[x][y] == '/' )continue;
            auto p = make_pair(x, y);
            for (int k = 0; k < 4; k++) {
                int nx = x + fx[k][0];
                int ny = y + fx[k][1];
                if ( nx < 0 || nx >= n || ny < 0 || ny >= m || G[nx][ny] == '/' )continue;
                if(Merge(p, make_pair(nx, ny)))
                cerr << "Merge" << G[p.first][p.second] << " and " << G[nx][ny] << endl;

            }
        }
    }
    cout << "Cnt=" << Count() << endl;
    return 0;
}
/**
这段代码实现了一个并查集算法来计算一个图的连通块数。

首先定义了一个矩阵表示的平面图G，其中'/'表示空格。

然后定义了一个并查集，其中F[i][j]表示(i,j)这个点所在的集合的根节点。初始时每个节点都是自己的根节点。

接着对于每个非空格的点，将其四个方向上可以连接的点合并到一个集合中。具体的实现是用Find函数找到这些点当前所在的集合的根节点，然后将其中任意一个点的根节点改为另一个点的根节点即可。如果两个点原本已经在一个集合中，则说明它们已经连通，不需要再合并，返回false。

最后遍历一遍所有点，对于每个点，如果它的根节点正好是自己，说明这是一个集合的根节点，记录连通块数+1。

返回最终的连通块数。*/